package binarySearchTree;

import java.util.Random;

//二叉搜索树类
public class BinarySearchTree {
    //二叉搜索树的结点
    static class TreeNode {
        private int key;            //结点的值
        private TreeNode left;      //左孩子
        private TreeNode right;     //右孩子
        //构造函数
        TreeNode(int key) {
            this.key = key;
        }
    }

    private TreeNode root;   //根节点

    //无参构造
    public BinarySearchTree(){
        this(null);
    }
    //有参构造
    public BinarySearchTree(TreeNode root) {
        this.root = root;
    }

    public TreeNode getRoot() {
        return root;
    }

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
        //空树，用key创建的节点作为根节点
        if(root == null){
            root = new TreeNode(key);
        }
        //非空树
        TreeNode parent = null;
        TreeNode cur = root;
        //从根结点开始查找插入的位置
        while(cur != null){
            //key小于当前结点的值，往左子树找
            if(key < cur.key){
                parent = cur;
                cur = cur.left;
                //key大于当前结点的值，往右子树找
            }else if(key > cur.key){
                parent = cur;
                cur = cur.right;
            }else{
                //树中已经插入key，无需再插入，插入失败，返回false
                return false;
            }
        }
        //找到了插入的位置，小于，作为parent的左孩子插入
        TreeNode newNode = new TreeNode(key);
        if(key < parent.key){
            parent.left = newNode;
        }else{  //大于，作为parent的右孩子插入
            parent.right = newNode;
        }
        //插入成功，返回true
        return true;
    }

    //查找key是否存在
    public TreeNode search(int key) {
        TreeNode cur = root;
        //从根结点开始查找
        while(cur != null){

            if(key < cur.key){
                //小于，往左子树找
                cur = cur.left;
            }else if(key > cur.key){
                //大于，往右子树找
                cur = cur.right;
            }else{
                return cur; //找到，返回该节点的引用
            }
        }
        //未找到。返回null
        return null;
    }
    //删除key的值
    public boolean remove(int key) {
        //空树，无结点可删除，删除失败，返回false
        if(root == null){
            return false;
        }
        //key 等于 根结点的值，删除根节点
        if(root.key == key){
            //1.左右子树为空，该树只有一个根结点
            if(root.left == null && root.right == null){
                root = null;
                return true;
            }
            //2.没有左子树
            if(root.left == null){
                root = root.right;
                return true;
            }
            //3.没有右子树
            if(root.right == null){
                root = root.left;
                return true;
            }
        }
        //右左子树均存在
        TreeNode parent = null;
        TreeNode cur = root;
        //从根结点开始查找要删除的结点
        while(cur != null){
            if(key < cur.key){
                //小于，往左子树查找
                parent = cur;
                cur = cur.left;
            }else if(key > cur.key){
                //大于，往右子树查找
                parent = cur;
                cur = cur.right;
            }else{  //key == cur.key，找到了要删除的结点，要删除的结点位置分4种情况进行删除
                // 1. 删除的是叶子节点（2和3可以处理1的情况）
                if(cur.left == null && cur.right == null){
                    //cur为parent的左孩子，parent左孩子置null
                    if(parent.left == cur){
                        parent.left = null;
                    }else{
                        //cur为parent的右孩子，parent右孩子置null
                        parent.right = null;
                    }
                    //删除成功，返回true
                    return true;
                }
                // 2. 删除的节点没有左子树
                if(cur.left == null){
                    //cur为parent的左孩子，将cur的右孩子作为parent左孩子
                    if(parent.left == cur){
                        parent.left = cur.right;
                    }else{
                        //cur为parent的右孩子，将cur的右孩子作为parent右孩子
                        parent.right = cur.right;
                    }
                    //删除成功，返回true
                    return true;
                }
                // 3. 删除的结点没有右子树
                if(cur.right == null){
                    //cur为parent的左孩子，将cur的左孩子作为parent左孩子
                    if(parent.left == cur){
                        parent.left = cur.left;
                    }else{
                        //cur为parent的右孩子，将cur的左孩子作为parent右孩子
                        parent.right = cur.left;
                    }
                    //删除成功，返回true
                    return true;
                }

                // 4. 删除的结点存在左右子树，
                // （1）找左子树的最大结点替换要删除的结点，删除左子树的最大结点
                // （2）或者找右子树的最小结点替换要删除的结点，删除右子树的最小结点
                // 这里以 找右子树的最小结点替换要删除的结点进行编写代码
                parent = cur;
                TreeNode goat = cur.right;
                //找到cur的右子树中的最小结点作为替罪羔羊，找到的goat是没有左子树的
                while(goat != null && goat.left != null){
                    parent = goat;
                    goat = goat.left;
                }
                //将删除结点的值替换为右子树的最小值
                cur.key = goat.key;

                //goat没有左子树
                if(parent.left == goat){
                    parent.left = goat.right;
                }else{
                    parent.right = goat.right;
                }
                //删除成功，返回true
                return true;
            }
        }
        return false;
    }

    //中序遍历打印结点的值
    public static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.key + " ");
        inOrder(root.right);
    }


    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
//        Random random = new Random(System.currentTimeMillis());
//        for(int i = 0; i < 10; i++){
//            tree.insert(random.nextInt(100) + 1);
//        }
//        inOrder(tree.root);
//        System.out.println();
//        tree.insert(10);
//        System.out.println(tree.search(10));
//        System.out.println(tree.remove(66));
//        System.out.println(tree.remove(10));
//        System.out.println(tree.remove(10));

        int[] arr = new int[]{15,89,22,11,3,7,4,95,100,5,13,77,6,10,53};
        for(int num : arr){
            tree.insert(num);
        }
        inOrder(tree.getRoot());
        System.out.println();
        System.out.println(tree.search(88));
        System.out.println(tree.search(89));
        for(int num : arr){
            System.out.println(tree.remove(num));
        }
        System.out.println(tree.remove(99));
        System.out.println(tree.remove(22));
    }
}